<!DOCTYPE html>
<html lang="en">
<head>
    <meta charset="UTF-8">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>插入排序</title>
</head>
<body>
    
</body>
<script>
    let array = [2,31,21,441,2,41,23,1,1,0,2,14,1,21]
    // 1.原版本
    // let insertSort = function(array){
    //     let arrayLength = array.length
    //     for(let i=1;i<arrayLength;i++) {
    //         let target = array[i]
    //         let j;
    //         for(j=i-1;j>=0;j--) {
    //             if(array[j] < target) {
    //                 break
    //             }
    //         }
    //         // 数组元素后移
    //         if(j!== i-1) {
    //             for(let k=i-1;k>j; k--) {
    //                 array[k+1] = array[k]
    //             }
    //             array[j+1] = target
    //         }        
    //     }
    // }

    // 2.简化版本
    // let insertSort = function(array){
    //     let arrayLength = array.length
    //     for(let i=1;i<arrayLength;i++){
    //         let target = array[i]
    //         let j;
    //         for(j=i-1;j>=0 && array[j] > target;j--){
    //             array[j+1] = array[j]
    //         }
    //         array[j+1] = target
    //     }
    // }

    // 3.使用 while 循环
    let insertSort = function(array){
        let arrayLength = array.length
        for(let i=1;i<arrayLength;i++) {
            let target = array[i]
            let j=i-1
            // while(j>0 && array[j-1] > target) {
            //     array[j] = array[j-1]
            //     j--
            // }
            // array[j] = target

            while(j>=0 && array[j] > target) {
                array[j+1] = array[j]
                j--
            }
            array[j+1] = target
        }
    }

    insertSort(array)
    console.log('输出插入排序后的内容:', array)
</script>
</html>